import java.util.HashMap;

public class question_20 {
}
//20 有效的括号
//思路是：栈+哈希表的映射
class Solution_20 {
    public boolean isValid(String s) {
//        第一步先判断长度是否为偶数，因为要一一对应
        if(s.length()%2!=0){
            return false;
        }
        char[] resource = s.toCharArray();
        char stack[]=new char[resource.length];
//      建立一个哈希表设置对应关系  '('，')'，'{'，'}'，'['，']'
//        让括号之间的对应关系相应的value相加等于7
        HashMap<String, Integer> map = new HashMap<>();
        map.put("(",1);
        map.put("{",2);
        map.put("[",3);
        map.put(")",6);
        map.put("}",5);
        map.put("]",4);
//        定义返回值，先定义返回值是false
//        栈顶位置
        int stack_top=-1;
        int i;
        for ( i = 0; i < resource.length; i++) {
            String temp=resource[i]+"";
//            说明是后半段
            if(map.get(temp)>3){
                if(stack_top==-1){
                    return false;
                }
//              说明栈顶有元素，就可以取得到，这是要判断是否匹配
                String temp_top=""+stack[stack_top];
//                不匹配
                if(map.get(temp)+map.get(temp_top)!=7){
                    return false;
                }else {
//                    匹配，栈顶元素出栈
                    stack_top--;
                }

            }else{
//                是前半段，直接加
                stack_top++;
                stack[stack_top]=resource[i];
            }
        }
        if(stack_top==-1&&i==resource.length){
            return true;
        }else {
            return false;
        }
    }
}
